//
//  SomeMp.c
//  DataStruct
//
//  Created by vase on 2022/3/29.
//

#include "SomeMp.h"


/** 字符串暴力匹配--https://leetcode-cn.com/problems/implement-strstr/*/
int simpleMP(char *haystack, char *needle) {
    int i = 0, j = 0;
    if (needle[j] == '\0') {
        return 0;  //特判子串为空
    }
    while (haystack[i]!='\0' && needle[j]!='\0') {
        if (haystack[i] == needle[j]) {
            //匹配成功，继续往前走
            i++;
            j++;
        }else {
            //匹配失败，回溯
            i = i - j + 1;
            j = 0;
        }
    }
    //如果子串确实走到最后，则说明匹配成功
    return needle[j]=='\0' ? i-j : -1;
}

/** 构建next数组，实现KMP算法，题源同上*/
int SimpleKMP(char *haystack, char *needle) {
    if (needle[0] == '\0') {
        return 0;  //特判子串为空
    }
    /** KMP算法需要先构建next数组*/
    int next[strlen(needle)];
    int head = 0, tail = 1; //设置前缀-后缀指针初始化位置
    next[0] = 0; //第一个字母的最大重叠前-后缀长度为0
    while (needle[tail] != '\0') {
        if (needle[head] == needle[tail]) {
            //如果前缀串和后缀串的最后一个字符匹配上，则可以在这里将头尾指针往后延伸
            head++;
            next[tail++] = head;
        }else if(head != 0){
            //如果没有匹配上，则需要按需折损一下前缀指针的长度
            head = next[head-1];
        }else {
            //如果头指针已经损耗殆尽，无法折损，或者说当前串不存在重合的前-后缀
            next[tail++] = 0;
        }
    }
    /** 使用next数组进行字符串匹配*/
    int i = 0, j = 0;
    //开始匹配
    while (haystack[i]!='\0' && needle[j]!='\0') {
        if (haystack[i] == needle[j]) {
            //匹配成功，继续往前走
            i++;
            j++;
        }else if(j != 0){
            //匹配失败，且尚未回到开头，还能回溯
            j = next[j-1];
        }else {
            //回到开头，重新匹配
            i++;
        }
    }
    //如果子串确实走到最后，则说明匹配成功
    return needle[j]=='\0' ? i-j : -1;
}
